#python实现各种排序算法
#http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html 排序算法稳定性分析
#http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

aryList = [30,70,20,10,40,60,50]

'''
https://www.cnblogs.com/kkun/archive/2011/11/23/2260280.html
冒泡 稳定排序
最好情况下的时间复杂度为O(n)；
最坏情况下的时间复杂度为O(n^2)；
'''
def bubble(arr):
    arr = arr[:]
    print('排序前',arr)
    arrLen = len(arr)
    for i in range(0,arrLen-1):
        for j in range(0,arrLen-i-1):#每执行一次 i 的循环已经找到最大的放在最后所以减i,因为是和相邻的比较所以减1
            if arr[j] > arr[j+1]:#升序
                arr[j],arr[j+1] = arr[j+1],arr[j]
    
    print('排序后',arr)
     
bubble(aryList)
print("原list",aryList)

#快速排序 http://developer.51cto.com/art/201403/430986.htm#topx
#是一种二分思想
def quick(arr,left,right):    
    if left < right:
        startVal = arr[left]
        i = left
        j = right
        while i!=j:#当i==j时表示跑完一趟和基准数(startVal)的比较交换了
            while arr[j]>=startVal and i<j: #寻找右边第一个小于基准数的位置            
                j = j - 1
            while arr[i]<=startVal and i<j: #寻找左边第一个大于基准数的位置
                i = i+1              
            if i < j:
                arr[i],arr[j] = arr[j],arr[i] #交换位置   
        arr[left] = arr[i]
        arr[i] = startVal        
        quick(arr,left,i-1) # 左边部分进行快排 跑完一趟比较之后 i 的位置是基准数 所以-1
        quick(arr,i+1,right) # 右边部分进行快排 跑完一趟比较之后 i 的位置是基准数 所以+1

qary = aryList[:]
quick(qary,0,len(aryList)-1)
print("快速排序结果",qary)

#直接插入排序
def insertSort(arr):    
    for i in range(0,len(arr)):
        temp = arr[i]
        j = i-1
        while(j>=0):            
            if arr[j] > temp: #前一个元素大于当前元素 则需要交换位置 
                arr[j+1] = arr[j]
            else:
                break       
            j = j - 1        
        arr[j+1] = temp

qary = aryList[:]
print(qary)
insertSort(qary)
print("insertSort结果",qary)